package com.leaves.leetcode.array.t1_Easy_twoSum;

import java.util.HashMap;
import java.util.Map;


/**
 * 核心要点：
 * 1、哈希表加速，原先i位置前的每个数字都要和i位置的数作比较，后的数字也一样。但hash表使这个耗时过程简化成了O(1)，促使提速
 */
class Solution {

    /**
     * 哈希表加速，原先i位置前的每个数字都要和i位置的数作比较，但hash表使这个耗时过程简化成了O(1)，促使提速
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) return new int[]{map.get(nums[i]), i};
            map.put(target - nums[i], i);
        }
        return new int[0];
    }


    /**
     * 暴力双重遍历
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumViolence(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[0];
    }
}